package com.wc.data_structures.sort;


import java.util.Arrays;

/**
 * @Author congge
 * @Date 2023/4/20 18:59
 * @description 排序工具类
 */

public class SortUtil {
    public static void main(String[] args) {
        int[] array = {3, 9, 111, 10, 3, 2, 3};
        SortUtil sortUtil = new SortUtil();
        System.out.println(Arrays.toString(array));
        sortUtil.radixSort(array);
        System.out.println(Arrays.toString(array));
    }


    /**
     * 冒泡排序
     *
     * @param array 待排序数组
     */
    public void bubbleSort(int[] array) {
        int n = array.length;
        // 检查是否交换过
        boolean sign;
        for (int i = 0; i < n - 1; i++) {

            sign = true;
            for (int j = 1; j < n - i; j++) {
                if (array[j] < array[j - 1]) {
                    swap(array, j, j - 1);
                    sign = false;
                }
            }
            // 如果没有交换就说明已经排好序了
            if (sign) {
                break;
            }
        }
    }

    /**
     * 选择排序
     *
     * @param array 待排序数组
     */
    public void selectSort(int[] array) {
        int n = array.length;
        // 存储最大值得下角标
        int maxIdx = n - 1;
        // 存储需要交换的下角标
        int curIdx = n - 1;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i; j++) {
                if (array[j] > array[maxIdx]) {
                    maxIdx = j;
                }
            }
            swap(array, maxIdx, curIdx);
            curIdx--;
        }
    }

    /**
     * 插入排序
     *
     * @param array 待排序数组
     */
    public void insertSort(int[] array) {
        int n = array.length;
        // 前面n个当前数
        int curIdx = 0;
        // 待插入数
        int insertNum;
        for (int i = 1; i < n; i++) {
            insertNum = array[i];
            while (curIdx >= 0 && insertNum < array[curIdx]) {
                array[curIdx + 1] = array[curIdx];
                curIdx--;
            }
            array[curIdx + 1] = insertNum;
            curIdx = i;
        }
    }

    /**
     * 希尔排序
     *
     * @param array 待排序数组
     */
    public void shellSort(int[] array) {
        int n = array.length;
        // 前一个数的下角标
        int curIdx;
        // 当前的插入数
        int insertNum;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 分成多少个组
            for (int i = 0; i < gap; i++) {
                curIdx = i;
                // 组里面插入排序
                for (int j = i + gap; j < n; j += gap) {
                    insertNum = array[j];
                    while (curIdx >= 0 && insertNum < array[curIdx]) {
                        array[curIdx + gap] = array[curIdx];
                        curIdx -= gap;
                    }
                    array[curIdx + gap] = insertNum;
                    curIdx = j;
                }
            }
        }
    }

    /**
     * 快速排序
     *
     * @param array 待排序数组
     */
    public void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 快速排序
     *
     * @param array 待排序数组
     * @param left  左边界
     * @param right 右面边界
     */
    public void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }

        int midNum = array[left];
        int i = left + 1;
        int j = right;

        while (true) {
            while (i < right && midNum > array[i]) i++;
            while (j > left && midNum < array[j]) j--;

            if (i >= j) {
                break;
            } else {
                swap(array, i, j);
                i++;
                j--;
            }
        }

        swap(array, j, left);
        quickSort(array, left, j - 1);
        quickSort(array, j + 1, right);
    }

    /**
     * 归并排序
     *
     * @param array 待排序数组
     */
    public void mergeSort(int[] array) {
        mergeSort(array, 0, array.length - 1, new int[array.length]);
    }

    /**
     * 分解 + 合并
     *
     * @param array 待排序数组
     * @param left  左边界
     * @param right 有边界
     * @param tmp   临时数组
     */
    public void mergeSort(int[] array, int left, int right, int[] tmp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            // 分解的左半截
            mergeSort(array, left, mid, tmp);
            // 分解的右面半截
            mergeSort(array, mid + 1, right, tmp);
            // 合并
            merge(array, left, mid, right, tmp);
        }
    }

    /**
     * 合并
     *
     * @param array 待排序数组
     * @param left  左边的初始索引
     * @param mid   中间索引
     * @param right 右边的索引
     * @param tmp   中转站
     */
    public void merge(int[] array, int left, int mid, int right, int[] tmp) {
        // 左边有序序列初始索引
        int i = left;
        // 右边有序序列初始索引
        int j = mid + 1;
        // 指向tmp数组当前索引
        int t = left;

        // 1、将有序索引填充到temp数组中去
        while (i <= mid && j <= right) {
            if (array[i] < array[j]) {
                tmp[t] = array[i++];
            } else {
                tmp[t] = array[j++];
            }
            t++;
        }
        // 2、将剩余数据填充到temp数组中
        while (i <= mid) {
            tmp[t++] = array[i++];
        }
        while (j <= right) {
            tmp[t++] = array[j++];
        }
        // 3、将tmp数组返回到tmp中区
//        t = 0;
        if (right + 1 - left >= 0) System.arraycopy(tmp, left, array, left, right + 1 - left);
    }

    /**
     * 基数排序
     * 堆内存溢出问题
     * 无法处理负数问题（将桶扩展，每一个基数 + 9 处理 将 -9~-1 放到0 ~ 8 的桶中）
     *
     * @param array 待排序数组
     */
    public void radixSort(int[] array) {
        int[][] bucket = new int[10][array.length];
        int[] countOfBucketElement = new int[10];

        // 求出最大位数
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            max = Math.max(array[i], max);
        }
        // 确定最大数的大小
        int len = (max + "").length();

        for (int round = 0, n = 1; round < len; round++, n *= 10) {
            // 将数据加入到桶中
            for (int k : array) {
                // 确定当前轮次的数
                int digitNum = k / n % 10;
                bucket[digitNum][countOfBucketElement[digitNum]] = k;
                countOfBucketElement[digitNum]++;
            }
            // 将桶中数据返回到原数组中
            for (int i = 0, idx = 0; i < 10; i++) {
                if (countOfBucketElement[i] != 0) {
                    for (int j = 0; j < countOfBucketElement[i]; j++) {
                        array[idx++] = bucket[i][j];
                    }
                    countOfBucketElement[i] = 0;
                }
            }
        }
    }


    /**
     * 交换数组位置元素
     *
     * @param array 待交换数组
     * @param i     待交换位置1
     * @param j     待交换位置2
     */
    public void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
